home *** CD-ROM | disk | FTP | other *** search
/ EnigmA Amiga Run 1996 March / EnigmA AMIGA RUN 05 (1996)(G.R. Edizioni)(IT)[!][issue 1996-03][Skylink CD IV].iso / earcd / program / ixemlsrc.lha / ixemul / static / fts.c < prev    next >
C/C++ Source or Header  |  1995-12-23  |  22KB  |  800 lines
  1. /*-
  2.  * Copyright (c) 1990 The Regents of the University of California.
  3.  * All rights reserved.
  4.  *
  5.  * Redistribution and use in source and binary forms, with or without
  6.  * modification, are permitted provided that the following conditions
  7.  * are met:
  8.  * 1. Redistributions of source code must retain the above copyright
  9.  *    notice, this list of conditions and the following disclaimer.
  10.  * 2. Redistributions in binary form must reproduce the above copyright
  11.  *    notice, this list of conditions and the following disclaimer in the
  12.  *    documentation and/or other materials provided with the distribution.
  13.  * 3. All advertising materials mentioning features or use of this software
  14.  *    must display the following acknowledgement:
  15.  *    This product includes software developed by the University of
  16.  *    California, Berkeley and its contributors.
  17.  * 4. Neither the name of the University nor the names of its contributors
  18.  *    may be used to endorse or promote products derived from this software
  19.  *    without specific prior written permission.
  20.  *
  21.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  22.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  23.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  24.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  25.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  26.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  27.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  28.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  29.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  30.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  31.  * SUCH DAMAGE.
  32.  */
  33.  
  34. #if defined(LIBC_SCCS) && !defined(lint)
  35. static char sccsid[] = "@(#)fts.c    5.19 (Berkeley) 5/9/91";
  36. #endif /* LIBC_SCCS and not lint */
  37.  
  38. #include <ixemul.h>
  39. #include <kprintf.h>
  40. #include <user.h>
  41. #include <sys/stat.h>
  42.  
  43. static inline int max (int a, int b) { return a < b ? a : b; }
  44.  
  45. #include <sys/cdefs.h>
  46. #include <fcntl.h>
  47. #include <dirent.h>
  48. #include "fts.h"
  49. #include <stdlib.h>
  50. #include <string.h>
  51. #include <unistd.h>
  52.  
  53. static FTSENT *fts_alloc(), *fts_build(), *fts_sort();
  54. static void fts_load(), fts_lfree();
  55. static u_short fts_stat();
  56. static char *fts_path();
  57.  
  58. #define    ISSET(opt)    (sp->fts_options & opt)
  59. #define    SET(opt)    (sp->fts_options |= opt)
  60.  
  61. #define    CHDIR(sp, path)    (!ISSET(FTS_NOCHDIR) && chdir(path))
  62. #define    FCHDIR(sp, fd)    (!ISSET(FTS_NOCHDIR) && fchdir(fd))
  63.  
  64. /* fts_build flags */
  65. #define    BCHILD        1        /* from fts_children */
  66. #define    BREAD        2        /* from fts_read */
  67.  
  68. FTS *
  69. fts_open(argv, options, compar)
  70.     char * const *argv;
  71.     register int options;
  72.     int (*compar)();
  73. {
  74.     register FTS *sp;
  75.     register FTSENT *p, *root;
  76.     register int nitems, maxlen;
  77.     FTSENT *parent, *tmp = NULL;
  78.     int len;
  79.  
  80.     /* Allocate/initialize the stream */
  81.     if (!(sp = (FTS *)malloc((u_int)sizeof(FTS))))
  82.         return(NULL);
  83.     bzero(sp, sizeof(FTS));
  84.     sp->fts_compar = compar;
  85.     sp->fts_options = options;
  86.  
  87.     /* Logical walks turn on NOCHDIR; symbolic links are too hard. */
  88.     if (ISSET(FTS_LOGICAL))
  89.         SET(FTS_NOCHDIR);
  90.  
  91.     /* Allocate/initialize root's parent. */
  92.     if (!(parent = fts_alloc(sp, "", 0)))
  93.         goto mem1;
  94.     parent->fts_level = FTS_ROOTPARENTLEVEL;
  95.  
  96.     /* Allocate/initialize root(s). */
  97.     maxlen = -1;
  98.     for (root = NULL, nitems = 0; *argv; ++argv, ++nitems) {
  99.         if (!(len = strlen(*argv))) {
  100.             errno = ENOENT;
  101.             KPRINTF (("&errno = %lx, errno = %ld\n", &errno, errno));
  102.             goto mem2;
  103.         }
  104.         if (maxlen < len)
  105.             maxlen = len;
  106.         p = fts_alloc(sp, *argv, len);
  107.         p->fts_level = FTS_ROOTLEVEL;
  108.         p->fts_parent = parent;
  109.         /*
  110.          * If comparison routine supplied, traverse in sorted
  111.          * order; otherwise traverse in the order specified.
  112.          */
  113.         if (compar) {
  114.             p->fts_link = root;
  115.             root = p;
  116.             p->fts_accpath = p->fts_name;
  117.             if (!(options & FTS_NOSTAT))
  118.                 p->fts_info = fts_stat(sp, p, 0);
  119.         } else {
  120.             p->fts_link = NULL;
  121.             if (!root)
  122.                 tmp = root = p;
  123.             else {
  124.                 tmp->fts_link = p;
  125.                 tmp = p;
  126.             }
  127.         }
  128.     }
  129.     if (compar && nitems > 1)
  130.         root = fts_sort(sp, root, nitems);
  131.  
  132.     /*
  133.      * Allocate a dummy pointer and make fts_read think that we've just
  134.      * finished the node before the root(s); set p->fts_info to FTS_NS
  135.      * so that everything about the "current" node is ignored.
  136.      */
  137.     if (!(sp->fts_cur = fts_alloc(sp, "", 0)))
  138.         goto mem2;
  139.     sp->fts_cur->fts_link = root;
  140.     sp->fts_cur->fts_info = FTS_NS;
  141.  
  142.     /* Start out with at least 1K+ of path space. */
  143.     if (!fts_path(sp, MAX(maxlen, MAXPATHLEN)))
  144.         goto mem3;
  145.  
  146.     /*
  147.      * If using chdir(2), grab a file descriptor pointing to dot to insure
  148.      * that we can get back here; this could be avoided for some paths,
  149.      * but almost certainly not worth the effort.  Slashes, symbolic links,
  150.      * and ".." are all fairly nasty problems.  Note, if we can't get the
  151.      * descriptor we run anyway, just more slowly.
  152.      */
  153.     if (!ISSET(FTS_NOCHDIR) && (sp->fts_rfd = open(".", O_RDONLY, 0)) < 0)
  154.         SET(FTS_NOCHDIR);
  155.  
  156.     return(sp);
  157.  
  158. mem3:    free(sp->fts_cur);
  159. mem2:    fts_lfree(root);
  160.     free(parent);
  161. mem1:    free(sp);
  162.     return(NULL);
  163. }
  164.  
  165. static void
  166. fts_load(sp, p)
  167.     FTS *sp;
  168.     register FTSENT *p;
  169. {
  170.     register int len;
  171.     register char *cp;
  172.  
  173.     /*
  174.      * Load the stream structure for the next traversal.  Since we don't
  175.      * actually enter the directory until after the preorder visit, set
  176.      * the fts_accpath field specially so the chdir gets done to the right
  177.      * place and the user can access the first node.
  178.      */
  179.     len = p->fts_pathlen = p->fts_namelen;
  180.     bcopy(p->fts_name, sp->fts_path, len + 1);
  181.     if ((cp = rindex(p->fts_name, '/')) && (cp != p->fts_name || cp[1])) {
  182.         len = strlen(++cp);
  183.         bcopy(cp, p->fts_name, len + 1);
  184.         p->fts_namelen = len;
  185.     }
  186.     p->fts_accpath = p->fts_path = sp->fts_path;
  187.  
  188.     p->fts_info = fts_stat(sp, p, 0);
  189.     sp->rdev = p->fts_statb.st_dev;
  190. }
  191.  
  192. int fts_close(sp)
  193.     FTS *sp;
  194. {
  195.     register FTSENT *freep, *p;
  196.     int saved_errno = 0;
  197.  
  198.     if (sp->fts_cur) {
  199.         /*
  200.          * This still works if we haven't read anything -- the dummy
  201.          * structure points to the root list, so we step through to
  202.          * the end of the root list which has a valid parent pointer.
  203.          */
  204.         for (p = sp->fts_cur; p->fts_level > FTS_ROOTPARENTLEVEL;) {
  205.             freep = p;
  206.             p = p->fts_link ? p->fts_link : p->fts_parent;
  207.             free(freep);
  208.         }
  209.         free(p);
  210.     }
  211.  
  212.     /* Free up child linked list, sort array, path buffer. */
  213.     if (sp->fts_child)
  214.         fts_lfree(sp->fts_child);
  215.     if (sp->fts_array)
  216.         free(sp->fts_array);
  217.     free(sp->fts_path);
  218.  
  219.     /* Return to original directory, save errno if necessary. */
  220.     if (!ISSET(FTS_NOCHDIR)) {
  221.         saved_errno = fchdir(sp->fts_rfd) ? errno : 0;
  222.         (void)close(sp->fts_rfd);
  223.     }
  224.  
  225.     /* Free up the stream pointer. */
  226.     free(sp);
  227.  
  228.     /* Set errno and return. */
  229.     if (!ISSET(FTS_NOCHDIR) && saved_errno) {
  230.         errno = saved_errno;
  231.         KPRINTF (("&errno = %lx, errno = %ld\n", &errno, errno));
  232.         return(-1);
  233.     }
  234.     return(0);
  235. }
  236.  
  237. /*
  238.  * Special case a root of "/" so that slashes aren't appended causing
  239.  * paths to be written as "//foo".
  240.  */
  241. #define    NAPPEND(p) \
  242.     (p->fts_level == FTS_ROOTLEVEL && p->fts_pathlen == 1 && \
  243.         p->fts_path[0] == '/' ? 0 : p->fts_pathlen)
  244.  
  245. FTSENT *
  246. fts_read(sp)
  247.     register FTS *sp;
  248. {
  249.     register FTSENT *p, *tmp;
  250.     register int instr;
  251.     register char *t;
  252.  
  253.     /* If finished or unrecoverable error, return NULL. */
  254.     if (!sp->fts_cur || ISSET(FTS_STOP))
  255.         return(NULL);
  256.  
  257.     /* Set current node pointer. */
  258.     p = sp->fts_cur;
  259.  
  260.     /* Save and zero out user instructions. */
  261.     instr = p->fts_instr;
  262.     p->fts_instr = FTS_NOINSTR;
  263.  
  264.     /* If used fts_link pointer for cycle detection, restore it. */
  265.     if (sp->fts_savelink) {
  266.         p->fts_link = sp->fts_savelink;
  267.         sp->fts_savelink = NULL;
  268.     }
  269.  
  270.     /* Any type of file may be re-visited; re-stat and re-turn. */
  271.     if (instr == FTS_AGAIN) {
  272.         p->fts_info = fts_stat(sp, p, 0);
  273.         return(p);
  274.     }
  275.  
  276.     /*
  277.      * Following a symlink -- SLNONE test allows application to see
  278.      * SLNONE and recover.
  279.      */
  280.     if (((instr == FTS_FOLLOW && (p->fts_info == FTS_SL)) ||
  281.         p->fts_info == FTS_SLNONE)) {
  282.         p->fts_info = fts_stat(sp, p, 1);
  283.         return(p);
  284.     }
  285.  
  286.     /* Directory in pre-order. */
  287.     if (p->fts_info == FTS_D) {
  288.         /* If skipped or crossed mount point, do post-order visit. */
  289.         if (instr == FTS_SKIP ||
  290.             (ISSET(FTS_XDEV) && p->fts_statb.st_dev != sp->rdev)) {
  291.             if (sp->fts_child) {
  292.                 fts_lfree(sp->fts_child);
  293.                 sp->fts_child = NULL;
  294.             }
  295.             p->fts_info = FTS_DP;
  296.             return(p);
  297.         } 
  298.  
  299.         /*
  300.          * Cd to the subdirectory, reading it if haven't already.  If
  301.          * the read fails for any reason, or the directory is empty,
  302.          * the fts_info field of the current node is set by fts_build.
  303.          * If have already read and now fail to chdir, whack the list
  304.          * to make the names come out right, and set the parent state
  305.          * so the application will eventually get an error condition.
  306.          * If haven't read and fail to chdir, check to see if we're
  307.          * at the root node -- if so, we have to get back or the root
  308.          * node may be inaccessible.
  309.          */
  310.         if (sp->fts_child) {
  311.             if (CHDIR(sp, p->fts_accpath)) {
  312.                 p->fts_parent->fts_cderr = errno;
  313.                 for (p = sp->fts_child; p; p = p->fts_link)
  314.                     p->fts_accpath =
  315.                         p->fts_parent->fts_accpath;
  316.             }
  317.         } else if (!(sp->fts_child = fts_build(sp, BREAD))) {
  318.             if ISSET(FTS_STOP)
  319.                 return(NULL);
  320.             if (p->fts_level == FTS_ROOTLEVEL &&
  321.                 FCHDIR(sp, sp->fts_rfd)) {
  322.                 SET(FTS_STOP);
  323.                 return(NULL);
  324.             }
  325.             return(p);
  326.         }
  327.         p = sp->fts_child;
  328.         sp->fts_child = NULL;
  329.         goto name;
  330.     }
  331.  
  332.     /* Move to next node on this level. */
  333. next:    tmp = p;
  334.     if ((p = p->fts_link)) {
  335.         free(tmp);
  336.  
  337.         /* If reached the top, load the paths for the next root. */
  338.         if (p->fts_level == FTS_ROOTLEVEL) {
  339.             fts_load(sp, p);
  340.             return(sp->fts_cur = p);
  341.         }
  342.  
  343.         /* User may have called fts_set on the node. */
  344.         if (p->fts_instr == FTS_SKIP)
  345.             goto next;
  346.         if (p->fts_instr == FTS_FOLLOW) {
  347.             p->fts_info = fts_stat(sp, p, 1);
  348.             p->fts_instr = FTS_NOINSTR;
  349.         }
  350.  
  351. name:        t = sp->fts_path + NAPPEND(p->fts_parent);
  352.         *t++ = '/';
  353.         bcopy(p->fts_name, t, p->fts_namelen + 1);
  354.         return(sp->fts_cur = p);
  355.     }
  356.  
  357.     /* Move up to the parent node. */
  358.     p = tmp->fts_parent;
  359.     free(tmp);
  360.  
  361.     if (p->fts_level == FTS_ROOTPARENTLEVEL) {
  362.         /*
  363.          * Done; free everything up and set errno to 0 so the user
  364.          * can distinguish between error and EOF.
  365.          */
  366.         free(p);
  367.         errno = 0;
  368.         KPRINTF (("&errno = %lx, errno = %ld\n", &errno, errno));
  369.         return(sp->fts_cur = NULL);
  370.     }
  371.  
  372.     sp->fts_path[p->fts_pathlen] = '\0';
  373.  
  374.     /*
  375.      * Cd back up to the parent directory.  If at a root node, have to cd
  376.      * back to the original place, otherwise may not be able to access the
  377.      * original node on post-order.
  378.      */
  379.     if (p->fts_level == FTS_ROOTLEVEL) {
  380.         if (FCHDIR(sp, sp->fts_rfd)) {
  381.             SET(FTS_STOP);
  382.             return(NULL);
  383.         }
  384.     }
  385.     else if (CHDIR(sp, "..")) {
  386.         SET(FTS_STOP);
  387.         return(NULL);
  388.     }
  389.  
  390.     /* 
  391.      * If had a chdir error when trying to get into the directory, set the
  392.      * info field to reflect this, and restore errno.  The error indicator
  393.      * has to be reset to 0 so that if the user does an FTS_AGAIN, it all
  394.      * works.
  395.      */
  396.     if (p->fts_cderr) {
  397.         errno = p->fts_cderr;
  398.         KPRINTF (("&errno = %lx, errno = %ld\n", &errno, errno));
  399.         p->fts_cderr = 0;
  400.         p->fts_info = FTS_ERR;
  401.     } else
  402.         p->fts_info = FTS_DP;
  403.     return(sp->fts_cur = p);
  404. }
  405.  
  406. /*
  407.  * Fts_set takes the stream as an argument although it's not used in this
  408.  * implementation; it would be necessary if anyone wanted to add global
  409.  * semantics to fts using fts_set.  An error return is allowed for similar
  410.  * reasons.
  411.  */
  412. /* ARGSUSED */
  413. int fts_set(sp, p, instr)
  414.     FTS *sp;
  415.     FTSENT *p;
  416.     int instr;
  417. {
  418.     p->fts_instr = instr;
  419.     return(0);
  420. }
  421.  
  422. FTSENT *
  423. fts_children(sp)
  424.     register FTS *sp;
  425. {
  426.     register FTSENT *p;
  427.     int fd;
  428.  
  429.     /* Set current node pointer. */
  430.     p = sp->fts_cur;
  431.  
  432.     /*
  433.      * Set errno to 0 so that user can tell the difference between an
  434.      * error and a directory without entries.  If not a directory being
  435.      * visited in *pre-order*, or we've already had fatal errors, return
  436.      * immediately.
  437.      */
  438.     errno = 0;
  439.     KPRINTF (("&errno = %lx, errno = %ld\n", &errno, errno));
  440.     if (ISSET(FTS_STOP) || (p->fts_info != FTS_D && p->fts_info != FTS_DNR))
  441.         return(NULL);
  442.  
  443.     /* Free up any previous child list. */
  444.     if (sp->fts_child)
  445.         fts_lfree(sp->fts_child);
  446.  
  447.     /*
  448.      * If using chdir on a relative path and called BEFORE fts_read does
  449.      * its chdir to the root of a traversal, we can lose -- we need to
  450.      * chdir into the subdirectory, and we don't know where the current
  451.      * directory is, so we can't get back so that the upcoming chdir by
  452.      * fts_read will work.
  453.      */
  454.     if (p->fts_level != FTS_ROOTLEVEL || p->fts_accpath[0] == '/' ||
  455.         ISSET(FTS_NOCHDIR))
  456.         return(sp->fts_child = fts_build(sp, BCHILD));
  457.  
  458.     if ((fd = open(".", O_RDONLY, 0)) < 0)
  459.         return(NULL);
  460.     sp->fts_child = fts_build(sp, BCHILD);
  461.     if (fchdir(fd))
  462.         return(NULL);
  463.     (void)close(fd);
  464.     return(sp->fts_child);
  465. }
  466.  
  467. /*
  468.  * This is the tricky part -- do not casually change *anything* in here.  The
  469.  * idea is to build the linked list of entries that are used by fts_children
  470.  * and fts_read.  There are lots of special cases.
  471.  *
  472.  * The real slowdown in walking the tree is the stat calls.  If FTS_NOSTAT is
  473.  * set and it's a physical walk (so that symbolic links can't be directories),
  474.  * we assume that the number of subdirectories in a node is equal to the number
  475.  * of links to the parent.  This allows stat calls to be skipped in any leaf
  476.  * directories and for any nodes after the directories in the parent node have
  477.  * been found.  This empirically cuts the stat calls by about 2/3.
  478.  */
  479. #define    ISDOT(a)    (a[0] == '.' && (!a[1] || (a[1] == '.' && !a[2])))
  480.  
  481. static FTSENT *
  482. fts_build(sp, type)
  483.     register FTS *sp;
  484.     int type;
  485. {
  486.     register struct dirent *dp;
  487.     register FTSENT *p, *head;
  488.     register int nitems;
  489.     FTSENT *cur;
  490.     DIR *dirp;
  491.     int cderr = 0, descend, len, level, maxlen, nlinks, saved_errno;
  492.     char *cp = NULL;
  493.  
  494.     /* Set current node pointer. */
  495.     cur = sp->fts_cur;
  496.  
  497.     /*
  498.      * Open the directory for reading.  If this fails, we're done.
  499.      * If being called from fts_read, set the fts_info field.
  500.      */
  501.     if (!(dirp = opendir(cur->fts_accpath))) {
  502.         if (type == BREAD)
  503.             cur->fts_info = FTS_DNR;
  504.         return(NULL);
  505.     }
  506.  
  507.     /*
  508.      * Nlinks is the number of possible entries of type directory in the
  509.      * directory if we're cheating on stat calls, 0 if we're not doing
  510.      * any stat calls at all, -1 if we're doing stats on everything.
  511.      */
  512.     nlinks =
  513.         ISSET(FTS_NOSTAT) && ISSET(FTS_PHYSICAL) ?
  514.         cur->fts_statb.st_nlink - (ISSET(FTS_SEEDOT) ? 0 : 2) : -1;
  515.  
  516.     /*
  517.      * If we're going to need to stat anything or we want to descend
  518.      * and stay in the directory, chdir.  If this fails we keep going.
  519.      * We won't be able to stat anything, but we can still return the
  520.      * names themselves.  Note, that since fts_read won't be able to
  521.      * chdir into the directory, it will have to return different path
  522.      * names than before, i.e. "a/b" instead of "b".  Since the node
  523.      * has already been visited in pre-order, have to wait until the
  524.      * post-order visit to return the error.  This is all fairly nasty.
  525.      * If a program needed sorted entries or stat information, they had
  526.      * better be checking FTS_NS on the returned nodes.
  527.      */
  528.     if (nlinks || type == BREAD)
  529.         if (FCHDIR(sp, dirfd(dirp))) {
  530.             if (type == BREAD)
  531.                 cur->fts_cderr = errno;
  532.             descend = nlinks = 0;
  533.             cderr = 1;
  534.         } else {
  535.             descend = 1;
  536.             cderr = 0;
  537.         }
  538.     else
  539.         descend = 0;
  540.  
  541.     /*
  542.      * Figure out the max file name length that can be stored in the
  543.      * current path -- the inner loop allocates more path as necessary.
  544.      * We really wouldn't have to do the maxlen calculations here, we
  545.      * could do them in fts_read before returning the path, but it's a
  546.      * lot easier here since the length is part of the dirent structure.
  547.      *
  548.      * If not changing directories set a pointer so that we can just
  549.      * append each new name into the path.
  550.      */
  551.     maxlen = sp->fts_pathlen - cur->fts_pathlen - 1;
  552.     len = NAPPEND(cur);
  553.     if (ISSET(FTS_NOCHDIR)) {
  554.         cp = sp->fts_path + len;
  555.         *cp++ = '/';
  556.     }
  557.  
  558.     level = cur->fts_level + 1;
  559.  
  560.     /* Read the directory, attaching each entry to the `link' pointer. */
  561.     for (head = NULL, nitems = 0; (dp = readdir(dirp));) {
  562.         if (!ISSET(FTS_SEEDOT) && ISDOT(dp->d_name))
  563.             continue;
  564.  
  565.         if (!(p = fts_alloc(sp, dp->d_name, (int)dp->d_namlen)))
  566.             goto mem1;
  567.         if (dp->d_namlen > maxlen) {
  568.             if (!fts_path(sp, (int)dp->d_namlen)) {
  569.                 /*
  570.                  * No more memory for path or structures.  Save
  571.                  * errno, free up the current structure and the
  572.                  * structures already allocated.
  573.                  */
  574. mem1:                saved_errno = errno;
  575.                 if (p)
  576.                     free(p);
  577.                 fts_lfree(head);
  578.                 (void)closedir(dirp);
  579.                 errno = saved_errno;
  580.                   KPRINTF (("&errno = %lx, errno = %ld\n", &errno, errno));
  581.                 cur->fts_info = FTS_ERR;
  582.                 SET(FTS_STOP);
  583.                 return(NULL);
  584.             }
  585.             maxlen = sp->fts_pathlen - sp->fts_cur->fts_pathlen - 1;
  586.         }
  587.  
  588.         p->fts_pathlen = len + dp->d_namlen + 1;
  589.         p->fts_parent = sp->fts_cur;
  590.         p->fts_level = level;
  591.  
  592.         if (nlinks) {
  593.             /* Build a file name for fts_stat to stat. */
  594.             if (ISSET(FTS_NOCHDIR)) {
  595.                 p->fts_accpath = p->fts_path;
  596.                 bcopy(p->fts_name, cp, p->fts_namelen + 1);
  597.             } else
  598.                 p->fts_accpath = p->fts_name;
  599.             p->fts_info = fts_stat(sp, p, 0);
  600.             if (nlinks > 0 && p->fts_info == FTS_D)
  601.                 --nlinks;
  602.         } else if (cderr) {
  603.             p->fts_info = ISSET(FTS_NOSTAT) ? FTS_NSOK : FTS_NS;
  604.             p->fts_accpath = cur->fts_accpath;
  605.         } else {
  606.             p->fts_accpath =
  607.                 ISSET(FTS_NOCHDIR) ? p->fts_path : p->fts_name;
  608.             p->fts_info = FTS_NSOK;
  609.         }
  610.  
  611.         p->fts_link = head;
  612.         head = p;
  613.         ++nitems;
  614.     }
  615.     (void)closedir(dirp);
  616.  
  617.     /*
  618.      * If not changing directories, reset the path back to original
  619.      * state.
  620.      */
  621.     if (ISSET(FTS_NOCHDIR)) {
  622.         if (cp - 1 > sp->fts_path)
  623.             --cp;
  624.         *cp = '\0';
  625.     }
  626.  
  627.     /*
  628.      * If descended after called from fts_children or called from
  629.      * fts_read and didn't find anything, get back.  If can't get
  630.      * back, we're done.
  631.      */
  632.     if (descend && (!nitems || type == BCHILD) && CHDIR(sp, "..")) {
  633.         cur->fts_info = FTS_ERR;
  634.         SET(FTS_STOP);
  635.         return(NULL);
  636.     }
  637.  
  638.     /* If we didn't find anything, just do the post-order visit */
  639.     if (!nitems) {
  640.         if (type == BREAD)
  641.             cur->fts_info = FTS_DP;
  642.         return(NULL);
  643.     }
  644.  
  645.     /* Sort the entries. */
  646.     if (sp->fts_compar && nitems > 1)
  647.         head = fts_sort(sp, head, nitems);
  648.     return(head);
  649. }
  650.  
  651. static u_short
  652. fts_stat(sp, p, follow)
  653.     FTS *sp;
  654.     register FTSENT *p;
  655.     int follow;
  656. {
  657.     int saved_errno;
  658.  
  659.     /*
  660.      * If doing a logical walk, or application requested FTS_FOLLOW, do
  661.      * a stat(2).  If that fails, check for a non-existent symlink.  If
  662.      * fail, return the errno from the stat call.
  663.      */
  664.     if (ISSET(FTS_LOGICAL) || follow) {
  665.         if (stat(p->fts_accpath, &p->fts_statb)) {
  666.             saved_errno = errno;
  667.             if (!lstat(p->fts_accpath, &p->fts_statb)) {
  668.                 errno = 0;
  669.                   KPRINTF (("&errno = %lx, errno = %ld\n", &errno, errno));
  670.                 return(FTS_SLNONE);
  671.             } 
  672.             errno = saved_errno;
  673.             KPRINTF (("&errno = %lx, errno = %ld\n", &errno, errno));
  674.             bzero(&p->fts_statb, sizeof(struct stat));
  675.             return(FTS_NS);
  676.         }
  677.     } else if (lstat(p->fts_accpath, &p->fts_statb)) {
  678.         bzero(&p->fts_statb, sizeof(struct stat));
  679.         return(FTS_NS);
  680.     }
  681.  
  682.     /*
  683.      * Cycle detection is done as soon as we find a directory.  Detection
  684.      * is by brute force; if the tree gets deep enough or the number of
  685.      * symbolic links to directories high enough something faster might
  686.      * be worthwhile.
  687.      */
  688.     if (S_ISDIR(p->fts_statb.st_mode)) {
  689.         register FTSENT *t;
  690.         register dev_t dev;
  691.         register ino_t ino;
  692.  
  693.         dev = p->fts_statb.st_dev;
  694.         ino = p->fts_statb.st_ino;
  695.         for (t = p->fts_parent; t->fts_level > FTS_ROOTLEVEL;
  696.             t = t->fts_parent)
  697.             if (ino == t->fts_statb.st_ino &&
  698.                 dev == t->fts_statb.st_dev) {
  699.                 sp->fts_savelink = p->fts_link;
  700.                 p->fts_link = t;
  701.                 return(FTS_DC);
  702.             }
  703.         return(FTS_D);
  704.     }
  705.     if (S_ISLNK(p->fts_statb.st_mode))
  706.         return(FTS_SL);
  707.     if (S_ISREG(p->fts_statb.st_mode))
  708.         return(FTS_F);
  709.     return(FTS_DEFAULT);
  710. }
  711.  
  712. #define    R(type, nelem, ptr) \
  713.     (type *)realloc((void *)ptr, (u_int)((nelem) * sizeof(type)))
  714.  
  715. static FTSENT *
  716. fts_sort(sp, head, nitems)
  717.     FTS *sp;
  718.     FTSENT *head;
  719.     register int nitems;
  720. {
  721.     register FTSENT **ap, *p;
  722.  
  723.     /*
  724.      * Construct an array of pointers to the structures and call qsort(3).
  725.      * Reassemble the array in the order returned by qsort.  If unable to
  726.      * sort for memory reasons, return the directory entries in their
  727.      * current order.  Allocate enough space for the current needs plus
  728.      * 40 so we don't realloc one entry at a time.
  729.      */
  730.     if (nitems > sp->fts_nitems) {
  731.         sp->fts_nitems = nitems + 40;
  732.         if (!(sp->fts_array =
  733.             R(FTSENT *, sp->fts_nitems, sp->fts_array))) {
  734.             sp->fts_nitems = 0;
  735.             return(head);
  736.         }
  737.     }
  738.     for (ap = sp->fts_array, p = head; p; p = p->fts_link)
  739.         *ap++ = p;
  740.     qsort((void *)sp->fts_array, nitems, sizeof(FTSENT *), sp->fts_compar);
  741.     for (head = *(ap = sp->fts_array); --nitems; ++ap)
  742.         ap[0]->fts_link = ap[1];
  743.     ap[0]->fts_link = NULL;
  744.     return(head);
  745. }
  746.  
  747. static FTSENT *
  748. fts_alloc(sp, name, len)
  749.     FTS *sp;
  750.     char *name;
  751.     register int len;
  752. {
  753.     register FTSENT *p;
  754.  
  755.     /*
  756.      * Variable sized structures; the name is the last element so
  757.      * we allocate enough extra space after the structure to store
  758.      * it.
  759.      */
  760.     if (!(p = (FTSENT *)malloc((size_t)(sizeof(FTSENT) + len))))
  761.         return(NULL);
  762.     bcopy(name, p->fts_name, len + 1);
  763.     p->fts_namelen = len;
  764.     p->fts_path = sp->fts_path;
  765.     p->fts_instr = FTS_NOINSTR;
  766.     p->fts_cderr = 0;
  767.     p->fts_number = 0;
  768.     p->fts_pointer = NULL;
  769.     return(p);
  770. }
  771.  
  772. static void
  773. fts_lfree(head)
  774.     register FTSENT *head;
  775. {
  776.     register FTSENT *p;
  777.  
  778.     /* Free a linked list of structures. */
  779.     while ((p = head)) {
  780.         head = head->fts_link;
  781.         free(p);
  782.     }
  783. }
  784.  
  785. /*
  786.  * Allow essentially unlimited paths; certain programs (find, rm, ls) need to
  787.  * work on any tree.  Most systems will allow creation of paths much longer
  788.  * than MAXPATHLEN, even though the kernel won't resolve them.  Add an extra
  789.  * 128 bytes to the requested size so that we don't realloc the path 2 bytes
  790.  * at a time.
  791.  */
  792. static char *
  793. fts_path(sp, size)
  794.     FTS *sp;
  795.     int size;
  796. {
  797.     sp->fts_pathlen += size + 128;
  798.     return(sp->fts_path = R(char, sp->fts_pathlen, sp->fts_path));
  799. }
  800.